Линейная задача о дополнительности

Линейная задача о дополнительности (LCP) — задача математической теории оптимизации, часто возникающая в вычислительной механике и охватывающая хорошо известное квадратичное программирование как частный случай. Задача был предложен Коттлом и Данцигом в 1968 году.

Формулировка

Даны действительные матрица M и вектор q. Задача линейной дополнительности (LCP) предусматривает определение по (q, M) векторов z и w, которые удовлетворяют следующим ограничениям:

• $w,z\geqslant 0,$ (то есть каждая компонента этих векторов неотрицательна)
• $z^{T}w=0$ или, что эквивалентно, $\sum \nolimits _{i}w_{i}z_{i}=0.$ Это условие из теории дополнительности, так как из него следует тот факт, что для всех $i$ хотя бы одна из величин $w_{i}$ и $z_{i}$ может быть положительна.
• $w=Mz+q$

Достаточным условием существования и единственности решения этой задачи является то, что матрица M должна быть симметричной положительно определённой. Если матрица M такова, что LCP (q, M) имеет решение для каждого q, то M является Q-матрицей. Если M таково, что LCP (q, M) имеет единственное решение для каждого q, то M является P-матрицей. Обе эти характеристики являются достаточными и необходимыми.

Вектор w является переменной рассогласования и поэтому она обычно отбрасывается после нахождения z. Таким образом, задача также может быть сформулирована следующим образом:

• $Mz+q\geqslant 0$
• $z\geqslant 0$
• $z^{\mathrm {T} }(Mz+q)=0$ (условие дополнительности)

Ссылки

• Björner, Anders. 10 Linear programming // Oriented Matroids / Anders Björner, Michel Las Vergnas, Bernd Sturmfels … [и др.]. — Cambridge University Press, 1999. — P. 417–479. — ISBN 978-0-521-77750-6. — doi:10.1017/CBO9780511586507.
• Cottle, R. W.; Dantzig, G. B. (1968). "Complementary pivot theory of mathematical programming". Linear Algebra and Its Applications. 1: 103—125. doi:10.1016/0024-3795(68)90052-9.
• Cottle, Richard W. The linear complementarity problem / Richard W. Cottle, Jong-Shi Pang, Richard E. Stone. — Boston, MA : Academic Press, Inc., 1992. — P. xxiv+762 pp. — ISBN 978-0-12-192350-1.
• Cottle, R. W.; Pang, J.-S.; Venkateswaran, V. (March-April 1989). "Sufficient matrices and the linear complementarity problem". Linear Algebra and Its Applications. 114—115: 231—249. doi:10.1016/0024-3795(89)90463-1. MR 0986877.{{cite journal}}: Википедия:Обслуживание CS1 (формат даты) (ссылка)
• Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (PDF). Optimization Methods and Software. 21 (2): 247—266. doi:10.1080/10556780500095009. S2CID 24418835.
• Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365—370. doi:10.1007/BF01582581. MR 1286455. S2CID 21476636.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997. 79 (1—3): 369—395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint.
• den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). "The linear complementarity problem, sufficient matrices, and the criss-cross method" (PDF). Linear Algebra and Its Applications. 187: 1—14. doi:10.1016/0024-3795(93)90124-7.
• Murty, Katta G. (January 1972). "On the number of solutions to the complementarity problem and spanning properties of complementary cones" (PDF). Linear Algebra and Its Applications. 5 (1): 65—108. doi:10.1016/0024-3795(72)90019-5. hdl:2027.42/34188.
• Murty, K. G. Linear complementarity, linear and nonlinear programming. — Berlin : Heldermann Verlag, 1988. — Vol. 3. — ISBN Updated and free PDF version at Katta G. Murty's website.
• Taylor, Joshua Adam. Convex Optimization of Power Systems. — Cambridge University Press, 2015. — ISBN 9781107076877.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. Degeneracy in optimization problems. 46—47 (1): 203—233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.
• Todd, Michael J. (1985). "Linear and quadratic programming in oriented matroids". Journal of Combinatorial Theory. Series B. 39 (2): 105—133. doi:10.1016/0095-8956(85)90042-5. MR 0811116.